package preguntas;

import java.util.ArrayList;
import java.util.Vector;

public class ArbolBB{
    Integer raiz;
    ArbolBB subABizq;
    ArbolBB subABder;
    
    // Constructor de un arbol vacio
    public ArbolBB(){
        raiz = null;
        subABizq = null;
        subABder = null;
    }
    
    private boolean esVacio(){
        boolean vacio = true;        
        if (raiz != null)
            vacio = false;        
        return vacio;
    }
    
    public void insertar(Integer nuevo){
        if(esVacio()){
            raiz = new Integer(nuevo);
            subABizq = new ArbolBB();
            subABder = new ArbolBB();
        }else{
            if(nuevo < raiz)
                subABizq.insertar(nuevo);
            else if (nuevo > raiz)
                subABder.insertar(nuevo);
        }
    }
    
    public ArbolBB buscar(Integer x){
        ArbolBB buscado = null;        
        if(!esVacio()){
            if(x < raiz)
                buscado = subABizq.buscar(x);
            else if (x > raiz)
                buscado = subABder.buscar(x);
            else
                return this;  
        }        
        return buscado;
    }

    
    public ArrayList<Integer> recorridoEnAnchura(){
        Vector<ArbolBB> cola = new Vector<ArbolBB>();
        ArbolBB arbol;
       ArrayList<Integer> anchura=new ArrayList<Integer>();
        cola.add(this);
        while(!cola.isEmpty()){
            arbol = cola.elementAt(0);
            cola.remove(0);
            anchura.add(arbol.raiz);
          
            if (!arbol.subABizq.esVacio()) 
            	cola.add(arbol.subABizq );
            if (!arbol.subABder.esVacio()) 
            	cola.add(arbol.subABder );
        }        
        System.out.println();
        return anchura;
    }
    
    

    public ArbolBB desDer(){ 
    	ArbolBB  res; 
    	if(subABder.esVacio()) 
    		res = this; 
    	else res = subABder.desDer(); 
    	return res; 
    }
    
    
    

  

    public Integer eliminar(Integer d){ 
    	Integer res=null; if(!esVacio()) 
    		if(d.equals(raiz)){
    			res = raiz; 
    			int estado = raizEstado(); 
    			switch(estado){ 
    			case 0: 
    				raiz = null; 
    				subABizq = subABder = null; 
    				break; 
    			case 1: 
    				raiz = subABizq.raiz; 
    				subABder = subABizq.subABder; 
    				subABizq = subABizq.subABizq; 
    				break; 
    			case 2: 
    				raiz = subABder.raiz; 
    				subABizq = subABder.subABizq; 
    				subABder = subABder.subABder; 
    				break; 
    			case 3: 
    				ArbolBB arbol; 
    				arbol = subABizq.desDer(); 
    				raiz = arbol.raiz; 
    				arbol.eliminar(raiz); 
    				} 
    			}else{ 
    				res = subABizq.eliminar(d); 
    				if(res==null) 
    					res = subABder.eliminar(d); 
    				} 
    	return res; 
    } 



    private int raizEstado(){
    	int res; 
    	if(subABizq.esVacio()){ 
    		if(subABder.esVacio()) 
    			res = 0; 
    		else res = 2; 
    		}else if(subABder.esVacio()) 
    			res = 1; 
    		else res = 3; 
    	return res; 
    }
    
}